package 归并排序;

import java.util.Arrays;

public class 非递归实现归并排序 {
    //这个非递归 并没有 用到栈
    public static void mergeSort(int[] arr) {
        for (int i=1;i<arr.length;i*=2) {
            //i为每次分组排序中 组内的个数
            merge(arr,i);
        }
    }

    public static void merge(int[] arr,int gap) {
        int[] tmp=new int[arr.length];
        int k=0;

        int s1=0;
        int e1=s1+gap-1;
        int s2=e1+1;
        int e2=s2+gap-1 >= arr.length ? arr.length-1:s2+gap-1;;

        while (s2<arr.length) {

            while (s1<=e1 && s2<=e2) {
                if (arr[s1]<=arr[s2]) {
                    tmp[k++]=arr[s1++];
                }else {
                    tmp[k++]=arr[s2++];
                }
            }

            while (s1<=e1) {
                //将第一个区间的剩余元素拷贝到tmp数组中
                tmp[k++]=arr[s1++];
            }

            while (s2<=e2) {
                //将第二个区间的剩余元素拷贝到tmp数组中
                tmp[k++]=arr[s2++];
            }

            //大小为gap的两组结束排序，开始接下来的两组
            s1=e2+1;
            e1=s1+gap-1;
            s2=e1+1;
            e2=s2+gap-1 >= arr.length ? arr.length-1:s2+gap-1;
        }

        //当没有第二个归并段时，需要将第一个归并段拷贝即可
        while (s1<=arr.length-1) {
            tmp[k++]=arr[s1++];
        }

        //将最终结果拷贝给 arr
        for (int i = 0; i < tmp.length; i++) {
            arr[i]=tmp[i];
        }

    }

    public static void main(String[] args) {
        int[] arr={12,5,9,34,6,8,33,56,89,0,7,4,22,55,77};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));

    }
}
